package cn.xaut.动态规划;

import java.util.Arrays;

/**
 * 376. 摆动序列
 */
public class demo376 {

    public int wiggleMaxLength(int[] nums) {

        int len = nums.length;
        if (len < 2)
            return len;

        int up = 1, down = 1;
        for (int i = 1; i < len; i++) {
            if (nums[i] > nums[i - 1])
                up = down + 1;
            else if (nums[i] < nums[i - 1])
                down = up + 1;
        }

        return Math.max(up, down);
    }

    // ↓ 有问题
/*    public int wiggleMaxLength(int[] nums) {

        int len = nums.length;
        if (len <= 2)
            return len;

        // 初始化
        // dp[i] 表示 dp[0...i] 的最长摆动序列的长度
        int[] dp = new int[len + 1];

        // 基础状态
        dp[0] = 1;
        dp[1] = 2;
        
        // 状态转移
        int res = Integer.MIN_VALUE;
        for (int i = 2; i <= len; i++) {
            if ((nums[i - 2] - nums[i - 1]) * (nums[i - 1] - nums[i]) < 0) 
                dp[i] = dp[i - 1] + 1;
            else
                dp[i] = dp[i - 1];
            res = Math.max(res, dp[i]);
        }
        
        return res;
    }*/

    public static void main(String[] args) {

        System.out.println(new demo376().wiggleMaxLength(new int[]{1, 7, 4, 9, 2, 5}));  // 6
        System.out.println(new demo376().wiggleMaxLength(new int[]{1, 17, 5, 10, 13, 15, 10, 5, 16, 8}));  // 7
        System.out.println(new demo376().wiggleMaxLength(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9}));  // 2
    }
}
